import java.nio.ByteBuffer;
import java.nio.IntBuffer;
import java.util.logging.Logger;
/**
 * Simple implementation of HashMap, using ByteBuffer.
 * Each element of this map consist of 3 int : key, value and index of next elemet's key.
 * ByteBuffer is divided on two half: first of one contains the beginnings of lists, other - the next elements of each list.
 * It's important that the value = 0 means empty element.
 * 
 * @author a.troitskaya
 *
 */

public class BufferHashMap {
    private final int EMPTY_VALUE = 0;
    private final int EMPTY_NEXT = 0;
    private final int EMPTY_KEY = 0;
    private final int NUM_OF_BUCKETS = 5;
    private IntBuffer map;
    private int maxSize;
    private int size;
    private static final Logger logger = Logger.getLogger(BufferHashMap.class.getName());
    
    public BufferHashMap(ByteBuffer buff) {
    	this.map = buff.asIntBuffer();
    	int i = 0;
    	while (i <= map.capacity() - 3) {
    		map.put(i, EMPTY_KEY);
    		map.put(i + 1, EMPTY_VALUE);
    		map.put(i + 2, EMPTY_NEXT);
    		i = i + 3;
    	}
    	this.maxSize = map.capacity() / 3;
    	this.size = 0;
    }
    
    public void put(int key, int value) throws EmptyBufferException, IllegalPutException {
    	if (key == 0) {
    		throw new IllegalPutException(key);
    	}
    	int index = hash(key);
    	if (map.get(index + 1) == EMPTY_VALUE) {
    		map.put(index, key);
    		map.put(index + 1, value);
    		size++;
    		if (map.get(3*NUM_OF_BUCKETS+index) != EMPTY_KEY) {
    			map.put(index + 2, 3*NUM_OF_BUCKETS+index);
    		}
    	} else {
    		if (size < maxSize) {
    		    if (map.get(index + 2) == EMPTY_NEXT) {
    			    int i = 3*NUM_OF_BUCKETS + index;
    			    while (map.get(i) != EMPTY_KEY) {
    				    i = i + 3;
    			    }
    			    hashMapPut(i, index + 2, key, value);
    			    size++;
    		    } else {
    		    	while (map.get(index+2) != EMPTY_NEXT) {
        				index = map.get(index+2);
        			}
    		        int i = index;
    		        while ((i <= map.capacity()-3)&&(map.get(i) != EMPTY_KEY)) {
    		        	i = i + 3;
    		        }
    		        if (i > map.capacity() - 3) {
    		        	int j = 3*NUM_OF_BUCKETS+hash(key);
    		        	while ((j < index)&&(map.get(j) != EMPTY_KEY)) {
    		        		j = j + 3;
    		        	}
    		        	if (j >= index) {
    		        		throw new EmptyBufferException();
    		        	}
    		        	else {
    		        		hashMapPut(j, index + 2, key, value);
    		        		size++;
    		        		return;
    		        	}
    		        }
    		    	hashMapPut(i, index + 2, key, value);
    		    	size++;
    		    }
    		} else {
                  throw new EmptyBufferException();
    		}
    	}
    }
    
    public int getValue(int key) throws NoSuchElementException {
    	int index = hash(key);
    	if (map.get(index) == EMPTY_KEY) {
    		throw new NoSuchElementException(key);
    	} else {
    		if (map.get(index) == key) {
    			return map.get(index + 1);
    		}
    	}
    	int searchKey = map.get(index);
    	while ((searchKey != key)&&(searchKey != EMPTY_KEY)&&(map.get(index+2) != EMPTY_NEXT)) {
    		index = map.get(index + 2);
    		searchKey = map.get(index);
    	}
    	if (searchKey == EMPTY_KEY) {
    		throw new NoSuchElementException(key);
    	} else {
    		if ((map.get(index + 2) == EMPTY_NEXT)&&(searchKey != key)) {
    			throw new NoSuchElementException(key);
    		} else {
    		    return map.get(index + 1);
    		}
    	}
    }
    
    private void hashMapPut(int indNext,int indPrev, int key, int value) {
    	map.put(indNext, key);
    	map.put(indNext + 1, value);
    	map.put(indNext + 2, EMPTY_NEXT);
    	map.put(indPrev, indNext);
    }
    
    private int hash(int key) {
    	return 3*(key % NUM_OF_BUCKETS);
    }
    
    public void remove(int key) throws NoSuchElementException {
    	int index = hash(key);
    	int PrevInd = EMPTY_KEY;
    	if (map.get(index) == EMPTY_KEY) {
    		int i = 3*NUM_OF_BUCKETS+index;
    		while ((i <= map.capacity() - 3)&&(map.get(i) == EMPTY_KEY)) {
    			i = i + 3;
    		}
    		if (i > map.capacity() - 3) {
    			throw new NoSuchElementException(key);
    		}
    		else {
    			index = i;
    		}
    	} else {
    		if (map.get(index) == key) {
                map.put(index, EMPTY_KEY);
                map.put(index + 1, EMPTY_VALUE);
                map.put(index + 2, EMPTY_NEXT);
                size--;
                return;
    		}
    	}
    	int searchKey = map.get(index);
    	boolean flag = false;
    	while ((searchKey != key)&&(searchKey != EMPTY_KEY)&&(map.get(index + 2) != EMPTY_NEXT)) {
    		PrevInd = index;
    		index = map.get(index + 2);
    		searchKey = map.get(index);
    		flag = true;
    	}
    	if (searchKey == EMPTY_KEY) {
    		throw new NoSuchElementException(key);
    	} else {
    		if ((map.get(index + 2) == EMPTY_NEXT)&&(searchKey != key)) {
    			throw new NoSuchElementException(key);
    		} else {
    			if (flag) {
    		        map.put(PrevInd + 2, map.get(index + 2));
    			}
    			map.put(index, EMPTY_KEY);
                map.put(index + 1, EMPTY_VALUE);
                map.put(index + 2, EMPTY_NEXT);
                size--;
    		}
    	}
    
    }
    public void printMap() {
    	int i = 0;
    	while (i <= map.capacity() - 3) {
    		logger.info("key "+map.get(i)+" value "+map.get(i+1)+" next "+map.get(i+2));
    		i = i + 3;
    	}
    }
}
